#include <stdio.h>
#include <stdlib.h>

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

typedef struct tag{
    BiTree p; //树的某个结点的地址值
    struct tag *pnext;
}tag,*p_tag;

// 队列的结构体
typedef BiTree ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear; //链表头，链表尾 ，队头队尾
}LinkQueue;  //先进先出

//队列初始化，使用的是带头结点的链表来实现
void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next=NULL;  //头结点的next指针为NULL
}
//判断队列是否为空
bool IsEmpty(LinkQueue Q)
{
    if(Q.front==Q.rear)
    {
        return true;
    } else{
        return false;
    }
}
//入队
void EnQueue(LinkQueue &Q,ElemType x)
{
    LinkNode *pnew=(LinkNode*)malloc(sizeof(LinkNode));
    pnew->data=x;
    pnew->next=NULL;    //要让next为NULL，这样才知道尾节点在哪结束
    Q.rear->next=pnew;  //尾指针的next要指向pnew，因为从尾部入队
    Q.rear=pnew;  //rear要指向新的尾部
}
//出队
bool DeQueue(LinkQueue &Q,ElemType &x)
{
    if(Q.front==Q.rear)
    {
        return false;
    }
    LinkNode *q=Q.front->next;
    x=q->data;    //获取要出队的元素值
    Q.front->next=q->next;  //让结点断链
    if(Q.rear==q)           //链表只剩下一个结点时，被删除后要改变rear
    {
        Q.rear=Q.front;
    }
    free(q);
    return true;
}

void PreOrder(BiTree p)
{
    if(p!=NULL)
    {
        printf("%c",p->c);
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}
void InOrder(BiTree p)
{
    if(p!=NULL)
    {
        InOrder(p->lchild);
        printf("%c",p->c);
        InOrder(p->rchild);
    }
}
void PostOrder(BiTree p)
{
    if(p!=NULL)
    {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        printf("%c",p->c);
    }
}
void LevelOrder(BiTree T)
{
    LinkQueue Q; //辅助队列
    InitQueue(Q); //初始化队列
    BiTree p; //存储出队的结点
    EnQueue(Q,T);
    while (!IsEmpty(Q))
    {
        DeQueue(Q,p);
        putchar(p->c); //等价于printf("%c",c);
        if(p->lchild)
        {
            EnQueue(Q,p->lchild); //左孩子不为空，就入队左孩子
        }
        if(p->rchild)
        {
            EnQueue(Q,p->rchild); //右孩子不为空，就入队右孩子
        }
    }
}
int main() {
    BiTree pnew;
    BiTree tree=NULL;
    p_tag ptail=NULL,phead=NULL,pcur,list_pnew=NULL;

    char c;
    while (scanf("%c",&c))
    {
        if(c=='\n')
        {
            break;   //读取换行就结束
        }
        pnew=(BiTree)calloc(1,sizeof(BiTNode));
        pnew->c=c;
        list_pnew=(p_tag)calloc(1,sizeof(tag));
        list_pnew->p=pnew;
        if(tree==NULL)
        {
            tree=pnew;
            phead=list_pnew;
            ptail=list_pnew;
            pcur=list_pnew;
        } else{
            ptail->pnext=list_pnew;
            ptail=list_pnew;
            if(pcur->p->lchild==NULL)
            {
                pcur->p->lchild=pnew;
            } else if(pcur->p->rchild==NULL)
            {
                pcur->p->rchild=pnew;
                pcur=pcur->pnext;
            }
        }
    }
//    PreOrder(tree);
//    printf("\n");
    InOrder(tree);
    printf("\n");
    PostOrder(tree);
    printf("\n");
    LevelOrder(tree);
    return 0;
}
